Programmable logic devices (PLDs), such as field programmable gate arrays (FPGAs) or complex programmable logic devices (CPLDs), may be programmed to provide various user-defined features. For example, a PLD may be implemented with look up tables (LUTs) configured to provide logic operations corresponding to a logic design specified by configuration data programmed into configuration memory of the PLD. These logic operations may be initially identified by a netlist that specifies the logical relationships and connections between LUTs of the PLD. Such connections and relationships may be visualized using directed acyclic graphs (DAGs) as such graphs are known in the art.
After a netlist is prepared, it is processed by appropriate software to prepare configuration data for programming into the PLD. Generally, this processing includes attempts to collapse one or more of the connections between the LUTs in order to simplify the configuration of the PLD. For example, one or more connections between the LUTs may be collapsed in order to reduce the number of connections, number of LUTs, signal path lengths, and/or number of logic levels used by the design. This can reduce the complexity of the logic design implemented by the PLD.
Unfortunately, conventional LUT connection collapsing processes typically consider very limited criteria in deciding whether to collapse LUT connections, thus resulting in logic designs that fail to satisfy other performance attributes. For example, one known connection collapsing process collapses connections to reduce the number of logic levels of a logic design. However, by focusing exclusively on the number of logic levels, this approach ignores the effects such collapsing may have on other aspects of the logic design. For example, this approach may cause non-critical paths having large numbers of logic levels to be collapsed, while ignoring critical timing paths having few logic levels.
Another known connection collapsing process uses the maximum size LUTs available for a given PLD to collapse as many connections as possible, including connections with non-critical timing attributes. Nevertheless, the many large LUTs used by this approach consume significant PLD routing resources. Because a PLD may have significantly different routing resources for minimum size LUTs and maximum size LUTs, this approach can severely impact the routing delays associated with critical timing paths.
As a result, there is a need for an improved approach to the collapsing of LUT-based connections that considers a variety of criteria. In particular, there is a need for such an approach for use with PLDs.